package test.coordinate;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Calculate the coordinate vlaue to position tree nodes
 * 
 *                 Root
 *  +---------------+------- ---+--------+
 *  |               |           |        |
 * Left children   Middle      Right Children
 * 
 * @author ginger
 *
 */
public class TreeCoordinator {

	public int postOrderWeightWalk(TreeNode node) {
		int leftWeight = 0;
		int rightWeight = 0;
		if (node.getLeftChildren() != null) {
			for (TreeNode childNode : node.getLeftChildren()) {
				leftWeight += postOrderWeightWalk(childNode);
			}
		}
		
		if (node.getRightChildren() != null) {
			for (TreeNode childNode : node.getRightChildren()) {
				rightWeight += postOrderWeightWalk(childNode);
			}
		}

		node.setLeftWeight(leftWeight);
		node.setRightWeight(rightWeight);
		int weight = leftWeight + rightWeight + 1;
		node.setWeight(weight);
		return weight;
	}
	
	public void preOrderCooridateWalk(TreeNode node, int x, int y) {
		node.setCoordX(x);
		node.setCoordY(y);
		if (node.getLeftChildren() != null) {
			int width = x - node.getLeftWeight();
			for (TreeNode childNode : node.getLeftChildren()) {
				preOrderCooridateWalk(childNode, width + childNode.getLeftWeight(), y + 1);
				width += childNode.getWeight();
			}
		}
		if (node.getMiddleChild() != null) {
			preOrderCooridateWalk(node.getMiddleChild(), x, y + 1);
		}
		if (node.getRightChildren() != null) {
			int width = 0;
			for (TreeNode childNode : node.getRightChildren()) {
				preOrderCooridateWalk(childNode, x + width + childNode.getLeftWeight() + 1, y + 1);
				width += childNode.getWeight();
			}
		}
	}
	
	public void printTree(TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<TreeNode>(); 
		queue.add(root);
		
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			System.out.println(node.getName() + " coord(" + node.getCoordX() + "," + node.getCoordY() + ") - weight[" + node.getLeftWeight()+ "," + node.getRightWeight() + "]");
			if (node.getLeftChildren()!= null) {
				for (TreeNode child : node.getLeftChildren()) {
					queue.add(child);
				}
			}
			if (node.getMiddleChild() != null) {
				queue.add(node.getMiddleChild());
			}
			if (node.getRightChildren()!= null) {
				for (TreeNode child : node.getRightChildren()) {
					queue.add(child);
				}
			}
		}
	}
	
	private TreeNode constructTree() {
		TreeNode root = new TreeNode("Root-4-1");
		TreeNode childNode1 = new TreeNode("Node-1-3");
		TreeNode childNode2 = new TreeNode("Node-2-3");
		TreeNode childNode = new TreeNode("Node-2-2");
		childNode.getLeftChildren().add(childNode1);
		childNode.setMiddleChild(childNode2);
		root.getLeftChildren().add(childNode);
		root.getLeftChildren().add(new TreeNode("Node-3-2"));
		root.setMiddleChild(new TreeNode("Node-4-2"));
		childNode1 = new TreeNode("Node-5-3");
		childNode2 = new TreeNode("Node-7-3");
		childNode = new TreeNode("Node-6-2");
		childNode.getLeftChildren().add(childNode1);
		childNode.getRightChildren().add(childNode2);
		root.getRightChildren().add(childNode);
		root.getRightChildren().add(new TreeNode("Node-8-2"));
		return root;
	}
	
	public static void main(String[] args) {
		TreeCoordinator treeCoordinator = new TreeCoordinator();
		TreeNode root = treeCoordinator.constructTree();
		treeCoordinator.postOrderWeightWalk(root);
		treeCoordinator.preOrderCooridateWalk(root, root.getLeftWeight() + 1, 1);
		treeCoordinator.printTree(root);
	}
}
